package SecondWeek;

import java.util.HashMap;
import java.util.Map;

public class Friday {
    // 1314.矩阵区域和
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length,n = mat[0].length;
        // 二维前缀和
        int[][] dp = new int[m + 1][n + 1];
        // 这里对 dp 预处理的时候呢，要注意，这里我们从mat取值的时候是从0,0下标开始的，但是dp存储是从1,1开始的
        // 所以我们要对其 取mat是要从原来的[i][j] -> [i - 1][j - 1]，这里的i，j是对dp所说的
        for (int i = 1;i <= m;i++) {
            for(int j = 1;j <= n;j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] + mat[i - 1][j - 1] - dp[i- 1][j - 1];
            }
        }
        int[][] ret = new int[m][n];
        // 这里的ret从dp中取值的话，同样需要注意下标，因为dp是从1,1开始的，ret从0,0开始
        // 所以当求x1，y1，x2，y2的时候呢，我们要将下标进行加1，才可以到dp中寻找，这里i，j是对ret所说的
        for (int i = 0;i < m;i++) {
            for(int j = 0;j < n;j++) {
                int x1 = Math.max(0,i - k) + 1;
                int y1 = Math.max(0,j - k) + 1;
                int x2 = Math.min(m - 1,i + k) + 1;
                int y2 = Math.min(n - 1,j + k) + 1;

                ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }
        return ret;
    }

    // 525.连续数组
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        // 哈希表中存在的是 <前缀和,下标>
        Map<Integer,Integer> map = new HashMap<>();
        // 这个是为了以防万一的，也不一定是会用上的
        map.put(0,-1); // 对于sum和为0的时候，就是从0-i这个位置为0，去这个下标前面去寻找的话，就是在-1下标，但是没有这个位置，所以默认为1

        int ret = 0,sum = 0;
        for (int i = 0;i < n;i++) {
            // 将原来的数组用的0转变成-1，这样当0和1是相同数量的时候呢，和就会为0，转变成寻找和为0的最长子数组
            sum += (nums[i] == 0 ? -1 : 1);
            if (map.containsKey(sum)) {
                // 如果这里存在就进行更新 ret，也就是长度
                ret = Math.max(ret,i - map.get(sum));
            }else {
                // 如果哈希表中不存在 sum，那么就存入，存在就不会进行更新
                map.put(sum,i);
            }
        }
        return ret;
    }

    // 974、和可被k整除的子数组
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1);

        int ret = 0,sum = 0;

        for (int num : nums) {
            sum += num;
            int r = (sum % k + k) % k; // 同余定理 和 负数余正数的修正
            ret += map.getOrDefault(r,0);
            map.put(r,map.getOrDefault(r,0) + 1);
        }

        return ret;
    }


    // 560、和为k的子数组
    public int subarraySum(int[] nums, int k) {
        //这里不能使用滑动窗口进行优化，因为存在负数和0，导致互惠出现单调性

        //前缀和+哈希表
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1); // 把 0 位置的值进行初始化为1，因为当前缀和刚好为k的时候，在之前找不到0，所以初始化
        int ret = 0;
        int sum = 0;
        for (int num : nums) {
            //这里的 sum 就是对应位置的前缀和，
            // dp[i] = dp[i - 1] + nums[i] -> dp[i] = sum + nums[i]，再把dp[i]赋值给sum
            // sum = sum + nums[i]
            sum += num;
            // 在dp[i]前缀和之前的区间[0,i-1]区间的前缀和中进行寻找和sum(dp[i])-k相等的值，对应的哈希表中Value值就是和为k的子数组的个数
            ret += map.getOrDefault(sum - k,0);
            // 查询完[0,i-1]区间之后，再把dp[i]位置的前缀和放入到哈希表中
            map.put(sum,map.getOrDefault(sum,0) + 1);
        }
        return ret;
    }

    // 238.除自身以外数组的乘积
    //这个题和下面的724 这个题是相似的，可以说是大差不差，但是边界是不一样的
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        //对于边界的处理
        f[0] = g[n - 1] = 1;

        for (int i = 1;i < n;i++) {
            f[i] = f[i - 1] * nums[i - 1];
        }
        for (int i = n - 2;i >= 0;i--) {
            g[i] = g[i + 1] * nums[i + 1];
        }
        int[] ret = new int[n];
        for (int i = 0;i < n;i++) {
            ret[i] = f[i] * g[i];
        }
        return ret;
    }

    // 724、寻找数组的中心下标
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        // 这个f数组是nums数组中[0,i-1]之间的和，前缀和
        int[] f = new int[n];
        // 这个g数组是nums数组中[i+1,n-1]之间的和，后缀和
        int[] g = new int[n];
        //初始化，要注意边界的情况，在f(从左到右)中 0 下标这个位置应为0，g(从右到左)中的n-1 下标这个位置应为0
        for (int i = 1;i < n;i++) {
            // f[i] 表示的是 nums 数组[0,i-1]这个区间的数据的和
            // f[i - 1]就是[0,i-2]区间的数据的和，加上i-1位置的数据就是f[i]对应的值
            // 比如: 1, 7, 3, 6, 5, 6
            // 下标为3位置的前缀和就是1 + 7 + 3
            // f[3] = f[3-1] + nums[3-1] -> (1+7) + 3 = 11
            f[i] = f[i - 1] + nums[i - 1];
        }

        for (int i = n - 2;i >= 0;i--) {
            // 和上面的前缀和分析的差不多，就是反过来理解
            g[i] = g[i + 1] + nums[i + 1];
        }

        //初始化结束，下面找出对应的数据，从左往右遍历下标，看是否存在 f[i] == g[i]，就是其中心下标
        for (int i = 0;i < n;i++) {
            if (f[i] == g[i]) {
                return i;
            }
        }
        return -1;
    }
}
